package first.niuke.simple;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @ClassName NC82
 * @description:
 * @author: 荣燊
 * @create: 2021-04-11 20:02
 **/
public class NC82 {
    // 滑动窗口的最大值
    public static void main(String[] args) {
        int[] a = {2,3,4,2,6,2,5,1};
        System.out.println(maxInWindows(a,3));
    }

    public static ArrayList<Integer> maxInWindows(int[] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if (num.length == 0 || size == 0 || num.length<size) {
            return null;
        }

        /**
         * 栈里面保存最大值，
         * 在窗口中，如果最大值在最右边出现，那么队列中只有一个最大值。
         * 在窗口中，如果最大值在最左边出现，那么队列中就会有最大值与次大值，或者其他的值
         * 最大值在窗口中间出现，那么就会有相应的判断,不止有最大值有次大值
         */
        Deque<Integer> deque = new LinkedList<>();
        for (int i=0; i<size; i++) {
            while (!deque.isEmpty() && deque.peekLast() < num[i]) {
                deque.pollLast();
            }
            deque.addLast(num[i]);
        }
        res.add(deque.peekFirst());

        for (int j=size; j<num.length; j++) {
            // 将窗口最左侧的值与队列中最大值比较,决定是否弹出最大值
            if (deque.peekFirst() == num[j-size]) {
                deque.removeFirst();
            }
            while (!deque.isEmpty() && deque.peekLast() < num[j]) {
                deque.pollLast();
            }
            deque.addLast(num[j]);

            res.add(deque.peekFirst());
        }

        return res;
    }
}
